Inverse Element in mod P

Fermat's minor theorem

$ a^{p-1}\equiv 1{\pmod {p}}

by transforming

$ a \times a^{p-2}\equiv 1{\pmod {p}}

therefore

$ a^{-1} \equiv a^{p-2} {\pmod {p}}

Fermat's minor theorem requires P to be prime

In this case, a and p need only be prime to each other

code:python

def mod_inverse_ee(a, m):

"""

Solve ax mod m = 1 with extended euclidean.

x = a^-1.

"""

x, y, g = extended_euclidean(a, m)

assert g == 1

return x % m

The inverse in modulo p of >n is from [Fermat's minor theorem

pow(n, p-2, p)

---